//
// Created by Administrator on 2023/11/3.
// https://www.luogu.com.cn/problem/P3912
// 八个通过两个超时
// 线性筛法
//

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n = 100;
    n = 1740948; // out: 130971
//    n = 2115790; //out:156902
//    cin>>n;
    // 保存是否素数信息
    bool isP[n + 1] = {0};
    // 保存素数在这个数组
    vector<int> ps;
    for (int i = 2; i <= n; ++i)
        isP[i] = 1;
    for (int i = 2; i <= n; ++i)
    {
        if (isP[i])
        {
            ps.push_back(i);
        }
        for (int j = 0; j < ps.size() && ps[j]*i<=n; ++j)
        {
            isP[ps[j]*i]=0;
            if(i%ps[j]==0)
                break;
        }
    }
    cout<<ps.size();
    return 0;
}